#include<iostream>
using namespace std;

void PrintMatrixIndex(int start, int end, int (*s)[6])
{
	if (start == end)
	{
		cout<< "A" << start;
	}
	else
	{
		cout<< "(";
		PrintMatrixIndex(start, s[start][end], s);
		PrintMatrixIndex(s[start][end] + 1, end, s);
		cout<< ")";
	}
}

int main(void)
{
	const int size = 6;
	int A[] = {30, 35, 15, 5, 10, 20, 25};

	int m[size][size] = {0};
	int s[size][size] = {0};

	for (int len = 1; len < size; len++)	//len+1 is the length of matrix chain
	{
		for (int i = 0; i < size - len; i++)	//i is the start pos
		{
			int j = i + len;					//j is the end pos

			for (int k = i; k < j; k++)
			{
				int q = m[i][k] + m[k + 1][j] + A[i] * A[k + 1] * A[j + 1];

				if (m[i][j] == 0 || q < m[i][j])
				{
					m[i][j] = q;
					s[i][j] = k;
				}
			}
		}
	}

	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			cout<< m[i][j] << "\t";
		}
		cout<< endl;
	}

	PrintMatrixIndex(0, 5, s);
}
